package two.chapter_5.c5_2;

import two.chapter_1.c1_3.LinkedQueue;
import two.chapter_1.c1_3.Queue;

/**
 * 单词查找树
 * @param <Value>
 */
public class TrieST<Value> implements StringST<Value> {

    private Node root;
    private static int R=256;


    /**
     * 构建单词查找树
     * @param key
     * @param value
     */
    @Override
    public void put(String key, Value value) {
        root=put(root,key,value,0);
    }

    private Node put(Node node, String key, Value value,int d) {
        if (node==null) return new Node();
        if (d==key.length()){//已经存在，更新val
            node.val=value;
            return node;
        }
        char c=key.charAt(d);//找到第d个字符所对应的子单词查找树
        node.next[c]=put(node.next[c],key,value,d+1);
        return node;
    }

    @Override
    public Value get(String key) {
        Node node=get(root,key,0);
        if (node==null){
            return null;
        }
        return (Value) node.val;
    }

    private Node get(Node node, String key,int d) {
        if (node==null){
            return null;
        }
        if (d==key.length()){
            return node;
        }
        char c=key.charAt(d);
        return get(node.next[c],key,d+1);
    }

    @Override
    public void delete(String key) {
        root=delete(root,key,0);
    }

    private Node delete(Node node, String key,int d) {
        if (node==null){
            return null;
        }
        if (d==key.length()){
            node.val=null;
        }else {
            char c=key.charAt(d);
            node.next[c]=delete(node.next[c],key,d+1);
        }
        if (node.val!=null) return node;
        for (char c=0;c<R;c++){
            if (node.next[c]!=null){
                return node;
            }
        }
        return null;
    }

    @Override
    public boolean contains(String key) {
        return false;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public String longestPrefixOf(String s) {
        int length=search(root,s,0,0);
        return s.substring(0,length);
    }

    private int search(Node node, String s,int d, int length) {
        if (node==null) return length;
        if (node.val!=null){
            length=d;
        }
        if (d==s.length()) return length;
        char c=s.charAt(d);
        return search(node.next[c],s,d+1,length);
    }


    @Override
    public Iterable<String> keysWithPrefix(String prefix) {
        Queue<String> q=new LinkedQueue<>();
        //获取前缀为prefix的子树
        Node sub=get(root,prefix,0);
        collect(sub,prefix,q);
        return q;
    }

    private void collect(Node node, String prefix, Queue<String> q) {
        if (node==null){
            return;
        }

        if (node.val!=null){
            q.enqueue(prefix);
        }
        for (char c = 0; c <R ; c++) {
            collect(node.next[c],prefix+c,q);
        }
    }

    @Override
    public Iterable<String> keysThatMatch(String pattern) {
        Queue<String> q=new LinkedQueue<>();

        return q;
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public Iterable<String> keys() {
        return keysWithPrefix("");
    }

    private static class Node{
        Object val;
        Node[] next;
        public Node(){
            next=new Node[R];
        }
    }
}
